package 数组算法;

import java.util.LinkedList;
import java.util.Queue;

public class numIslands200 {
    /**
     * 这是一个回溯问题
     *
     * @param grid
     * @return
     */
    // 表示四个方向
    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};

    /**
     * 岛屿问题
     *
     * @param grid
     * @return
     */
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                //表示是陆地分范围
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * 这是一个DFS算法，不需要的回溯来判断
     *
     * @param grid
     * @param i
     * @param j
     */
    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
            //表示超出返回同时排除 等于0的情况
            return;
        }
        // 如果不是的那就设置新的
        grid[i][j] = '0';
        // 开始遍历的四个方向
        for (int k = 0; k < 4; k++) {
            int new_i = dx[k] + i;
            int new_j = dy[k] + j;
            dfs(grid, new_i, new_j);
        }
    }

    private void dfsV2(char[][] grid, int i, int j) {
        // 表示超出范围
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) {
            //表示超出返回同时排除 等于0的情况
            return;
        }
        // 表示不是陆地
        if (grid[i][j] != '1') {
            return;
        }
        // 如果不是的那就设置新的
        grid[i][j] = '2';
        // 开始遍历的四个方向
        for (int k = 0; k < 4; k++) {
            int new_i = dx[k] + i;
            int new_j = dy[k] + j;
            dfsV2(grid, new_i, new_j);
        }
    }

    /**
     * @param grid
     * @return
     */
    public int numIslandsV1(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    private void bfs(char[][] grid, int i, int j) {
        Queue<int[]> list = new LinkedList<>();
        //如果是1 那就加入进来
        list.add(new int[]{i, j});
        //判断list是否为空
        while (!list.isEmpty()) {
            // 将list中的删除 记录原来的x y的坐标
            int[] cur = list.remove();
            i = cur[0];
            j = cur[1];
            // 如果是的在范围之内的话， 同时的数字为1表示的是这样
            if (0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') {
                grid[i][j] = '0';
                for (int k = 0; k < 4; k++) {
                    int new_i = dx[k] + i;
                    int new_j = dy[k] + j;
                    list.add(new int[]{new_i, new_j});
                }
            }
        }
    }
}
